/**
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 */
//滑动窗口解决
function findAnagrams(s, p) {
  let left=0, right=0, count=0, keys=0
  const res=[], map={}, w={}
  for(let c of p) {
    map[c]=(map[c]||0)+1
  }
  keys=Object.keys(map).length
  while(right<s.length) {
    const c=s[right++]
    if(map[c]) {
      w[c]=(w[c]||0)+1
      w[c]===map[c] && count++
    }
    while(right-left>=p.length){
      count===keys && res.push(left)
      const n=s[left++]
      if(w[n]!==undefined){
        w[n]===map[n] && count--
        w[n]--
      }
    }
  }
  return res
}
const s = "cbaebabacd"
const p = "abc"
console.log(findAnagrams(s, p))
/**
 * 思路：滑动窗口 + 哈希表
 * 1. 使用need记录p中每个字符需要的次数
 * 2. 使用window记录当前窗口中每个字符出现的次数,作用是统计窗口中每个字符出现的次数，如果窗口中每个字符出现的次数等于need中每个字符出现的次数，则说明找到了一个异位词
 * 3. 使用valid记录窗口中满足need条件的字符个数
 * 4. 当窗口大小等于p的长度时，检查valid是否等于needSize
 * 5. 如果相等，说明找到了一个异位词，记录起始位置
 * 时间复杂度：O(n)，其中n是s的长度
 * 空间复杂度：O(m)，其中m是p中不同字符的个数
 */